/**
 * Created by L.jp
 * Description:给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。
 * 这个路径必须满足以下条件：
 *
 * 1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
 * 2. 你不能走重复的单元格。即每个格子最多只能走一次。
 * User: 86189
 * Date: 2022-08-18
 * Time: 10:24
 */
public class Solution {
    //方向数组
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};
    private int n,m;
    public int solve (int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        //既然不能多次遍历的求出最长路径，那么就需要使用一个动态更新的数组取存储到达每一个位置的最长路径长度
        //dp数组含义表示每一个位置的最长路径长度
        int[][] dp=new int[n+1][m+1];
        //最长路径长度
        int ret=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                ret=Math.max(ret,dfs(matrix,dp,i,j));
            }
        }
        //最终的最长路径长度
        return ret;
    }
    
    //使用回溯+动归求出每个位置的最长路径长度
    private int dfs(int[][] matrix, int[][] dp,int i,int j) {
        if(dp[i][j]!=0){
            //当前位置已经被遍历过，那么就返当前位置的路径长度
            return dp[i][j];
        }
        dp[i][j]++;
        //遍历这个坐标四周
        for(int k=0;k<4;k++){
            int nexti=i+around[k][0];
            int nextj=j+around[k][1];
            //判断条件
            if(nexti>=0 && nexti<n && nextj>=0 && nextj<m && matrix[nexti][nextj]>matrix[i][j]){
                dp[i][j]=Math.max(dp[i][j],dfs(matrix,dp,nexti,nextj)+1);
            }
        }
        return dp[i][j];
    }
}
